home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / CompactShortArray.java < prev    next >
Text File  |  1998-09-22  |  15KB  |  406 lines
  1. /*
  2.  * @(#)CompactShortArray.java    1.9 97/10/28
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. /**
  34.  * class CompactATypeArray : use only on primitive data types
  35.  * Provides a compact way to store information that is indexed by Unicode
  36.  * values, such as character properties, types, keyboard values, etc.This
  37.  * is very useful when you have a block of Unicode data that contains
  38.  * significant values while the rest of the Unicode data is unused in the
  39.  * application or when you have a lot of redundance, such as where all 21,000
  40.  * Han ideographs have the same value.  However, lookup is much faster than a
  41.  * hash table.
  42.  * A compact array of any primitive data type serves two purposes:
  43.  * <UL type = round>
  44.  *     <LI>Fast access of the indexed values.
  45.  *     <LI>Smaller memory footprint.
  46.  * </UL>
  47.  * A compact array is composed of a index array and value array.  The index
  48.  * array contains the indicies of Unicode characters to the value array.
  49.  * @see                CompactByteArray
  50.  * @see                CompactIntArray
  51.  * @see                CompactCharArray
  52.  * @see                CompactStringArray
  53.  * @version            1.9 10/28/97
  54.  * @author             Helena Shih
  55.  */
  56. final class CompactShortArray implements Cloneable {
  57.  
  58.  
  59.     /**
  60.      * The total number of Unicode characters.
  61.      */
  62.     public static  final int UNICODECOUNT =65536;
  63.  
  64.     /**
  65.      * Default constructor for CompactShortArray, the default value of the
  66.      * compact array is 0.
  67.      */
  68.     public CompactShortArray()
  69.     {
  70.         this((short)0);
  71.     }
  72.     /**
  73.      * Constructor for CompactShortArray.
  74.      * @param defaultValue the default value of the compact array.
  75.      */
  76.     public CompactShortArray(short defaultValue)
  77.     {
  78.         int i;
  79.         values = new short[UNICODECOUNT];
  80.         indices = new short[INDEXCOUNT];
  81.         for (i = 0; i < UNICODECOUNT; ++i) {
  82.             values[i] = defaultValue;
  83.         }
  84.         for (i = 0; i < INDEXCOUNT; ++i) {
  85.             indices[i] = (short)(i<<BLOCKSHIFT);
  86.         }
  87.         isCompact = false;
  88.     }
  89.     /**
  90.      * Constructor for CompactShortArray.
  91.      * @param indexArray the indicies of the compact array.
  92.      * @param newValues the values of the compact array.
  93.      * @exception IllegalArgumentException If the index is out of range.
  94.      */
  95.     public CompactShortArray(short indexArray[],
  96.                              short newValues[])
  97.     {
  98.         int i;
  99.         if (indexArray.length != INDEXCOUNT)
  100.             throw new IllegalArgumentException("Index out of bounds.");
  101.         for (i = 0; i < INDEXCOUNT; ++i) {
  102.             short index = indexArray[i];
  103.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  104.                 throw new IllegalArgumentException("Index out of bounds.");
  105.         }
  106.         indices = indexArray;
  107.         values = newValues;
  108.     }
  109.     /**
  110.      * Get the mapped value of a Unicode character.
  111.      * @param index the character to get the mapped value with
  112.      * @return the mapped value of the given character
  113.      */
  114.     public short elementAt(char index) // parameterized on short
  115.     {
  116.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  117.                        + (index & BLOCKMASK)]);
  118.     }
  119.     /**
  120.      * Set a new value for a Unicode character.
  121.      * Set automatically expands the array if it is compacted.
  122.      * @param index the character to set the mapped value with
  123.      * @param value the new mapped value
  124.      */
  125.     public void setElementAt(char index, short value)
  126.     {
  127.         if (isCompact)
  128.             expand();
  129.         values[(int)index] = value;
  130.     }
  131.     /**
  132.      * Set new values for a range of Unicode character.
  133.      * @param start the starting offset of the range
  134.      * @param end the ending offset of the range
  135.      * @param value the new mapped value
  136.      */
  137.     public void setElementAt(char start, char end, short value)
  138.     {
  139.         int i;
  140.         if (isCompact) {
  141.             expand();
  142.         }
  143.         for (i = start; i <= end; ++i) {
  144.             values[i] = value;
  145.         }
  146.     }
  147.     /**
  148.       *Compact the array.
  149.       */
  150.     public void compact()
  151.     {
  152.         if (isCompact == false) {
  153.             char[]      tempIndex;
  154.             int                     tempIndexCount;
  155.             short[]         tempArray;
  156.             short           iBlock, iIndex;
  157.  
  158.             // make temp storage, larger than we need
  159.             tempIndex = new char[UNICODECOUNT];
  160.             // set up first block.
  161.             tempIndexCount = BLOCKCOUNT;
  162.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  163.                 tempIndex[iIndex] = (char)iIndex;
  164.             }; // endfor (iIndex = 0; .....)
  165.             indices[0] = (short)0;
  166.  
  167.             // for each successive block, find out its first position
  168.             // in the compacted array
  169.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  170.                 int     newCount, firstPosition, block;
  171.                 block = iBlock<<BLOCKSHIFT;
  172.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  173.                 firstPosition = FindOverlappingPosition(block, tempIndex,
  174.                                                         tempIndexCount);
  175.  
  176.                 newCount = firstPosition + BLOCKCOUNT;
  177.                 if (newCount > tempIndexCount) {
  178.                     for (iIndex = (short)tempIndexCount;
  179.                          iIndex < newCount;
  180.                          ++iIndex) {
  181.                         tempIndex[iIndex]
  182.                             = (char)(iIndex - firstPosition + block);
  183.                     } // endfor (iIndex = tempIndexCount....)
  184.                     tempIndexCount = newCount;
  185.                 } // endif (newCount > tempIndexCount)
  186.                 indices[iBlock] = (short)firstPosition;
  187.             } // endfor (iBlock = 1.....)
  188.  
  189.             // now allocate and copy the items into the array
  190.             tempArray = new short[tempIndexCount];
  191.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  192.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  193.             }
  194.             values = null;
  195.             values = tempArray;
  196.             isCompact = true;
  197.         } // endif (isCompact != false)
  198.     }
  199.     /** For internal use only.  Do not modify the result, the behavior of
  200.       * modified results are undefined.
  201.       */
  202.     public short getIndexArray()[]
  203.     {
  204.         return indices;
  205.     }
  206.     /** For internal use only.  Do not modify the result, the behavior of
  207.       * modified results are undefined.
  208.       */
  209.     public short getStringArray()[]
  210.     {
  211.         return values;
  212.     }
  213.     /**
  214.      * Overrides Cloneable
  215.      */
  216.     public Object clone()
  217.     {
  218.         try {
  219.             CompactShortArray other = (CompactShortArray) super.clone();
  220.             other.values = (short[])values.clone();
  221.             other.indices = (short[])indices.clone();
  222.             return other;
  223.         } catch (CloneNotSupportedException e) {
  224.             throw new InternalError();
  225.         }
  226.     }
  227.     /**
  228.      * Compares the equality of two compact array objects.
  229.      * @param obj the compact array object to be compared with this.
  230.      * @return true if the current compact array object is the same
  231.      * as the compact array object obj; false otherwise.
  232.      */
  233.     public boolean equals(Object obj) {
  234.         if (obj == null) return false;
  235.         if (this == obj)                      // quick check
  236.             return true;
  237.         if (getClass() != obj.getClass())         // same class?
  238.             return false;
  239.         CompactShortArray other = (CompactShortArray) obj;
  240.         for (int i = 0; i < UNICODECOUNT; i++) {
  241.             // could be sped up later
  242.             if (elementAt((char)i) != other.elementAt((char)i))
  243.                 return false;
  244.         }
  245.         return true; // we made it through the guantlet.
  246.     }
  247.     /**
  248.      * Generates the hash code for the compact array object
  249.      */
  250.  
  251.     public int hashCode() {
  252.         int result = 0;
  253.         int increment = Math.min(3, values.length/16);
  254.         for (int i = 0; i < values.length; i+= increment) {
  255.             result = result * 37 + values[i];
  256.         }
  257.         return result;
  258.     }
  259.     // --------------------------------------------------------------
  260.     // package private
  261.     // --------------------------------------------------------------
  262.     void writeArrays()
  263.     {
  264.         int i;
  265.         int cnt = ((values.length > 0) ? values.length :
  266.                    (values.length + UNICODECOUNT));
  267.         System.out.println("{");
  268.         for (i = 0; i < INDEXCOUNT-1; i++)
  269.         {
  270.             System.out.print("(short)" + (int)((getIndexArrayValue(i) >= 0) ?
  271.                 (int)getIndexArrayValue(i) :
  272.                 (int)(getIndexArrayValue(i)+UNICODECOUNT)) + ", ");
  273.             if (i != 0)
  274.                 if (i % 10 == 0)
  275.                     System.out.println();
  276.         }
  277.         System.out.println("(short)" +
  278.                            (int)((getIndexArrayValue(INDEXCOUNT-1) >= 0) ?
  279.                                  (int)getIndexArrayValue(i) :
  280.                                  (int)(getIndexArrayValue(i)+UNICODECOUNT)) +
  281.                            " }");
  282.         System.out.println("{");
  283.         for (i = 0; i < cnt-1; i++)
  284.         {
  285.             System.out.print("(short)" + (int)getArrayValue(i) + ", ");
  286.             if (i != 0)
  287.                 if (i % 10 == 0)
  288.                     System.out.println();
  289.         }
  290.         System.out.println("(short)" + (int)getArrayValue(cnt-1) + " }");
  291.     }
  292.     // Print char Array  : Debug only
  293.     void printIndex(short start, short count)
  294.     {
  295.         int i;
  296.         for (i = start; i < count; ++i)
  297.         {
  298.             System.out.println(i + " -> : " +
  299.                                (int)((indices[i] >= 0) ?
  300.                                      indices[i] :
  301.                                      indices[i] + UNICODECOUNT));
  302.         }
  303.         System.out.println();
  304.     }
  305.     void printPlainArray(int start,int count, char[] tempIndex)
  306.     {
  307.         int iIndex;
  308.         if (tempIndex != null)
  309.         {
  310.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  311.             {
  312.                 System.out.print(" " + (int)getArrayValue(tempIndex[iIndex]));
  313.             }
  314.         }
  315.         else
  316.         {
  317.             for (iIndex = start; iIndex < start + count; ++iIndex)
  318.             {
  319.                 System.out.print(" " + (int)getArrayValue(iIndex));
  320.             }
  321.         }
  322.         System.out.println("    Range: start " + start + " , count " + count);
  323.     }
  324.     // --------------------------------------------------------------
  325.     // private
  326.     // --------------------------------------------------------------
  327.     /**
  328.       * Expanding takes the array back to a 65536 element array.
  329.       */
  330.     private void expand()
  331.     {
  332.         int i;
  333.         if (isCompact) {
  334.             short[] tempArray;
  335.             tempArray = new short[UNICODECOUNT];
  336.             for (i = 0; i < UNICODECOUNT; ++i) {
  337.                 tempArray[i] = elementAt((char)i);
  338.             }
  339.             for (i = 0; i < INDEXCOUNT; ++i) {
  340.                 indices[i] = (short)(i<<BLOCKSHIFT);
  341.             }
  342.             values = null;
  343.             values = tempArray;
  344.             isCompact = false;
  345.         }
  346.     }
  347.     // # of elements in the indexed array
  348.     private short capacity()
  349.     {
  350.         return (short)values.length;
  351.     }
  352.     private short getArrayValue(int n)
  353.     {
  354.         return values[n];
  355.     }
  356.     private short getIndexArrayValue(int n)
  357.     {
  358.         return indices[n];
  359.     }
  360.     private int
  361.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  362.     {
  363.         int i;
  364.         short j;
  365.         short currentCount;
  366.  
  367.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  368.             printPlainArray(start, BLOCKCOUNT, null);
  369.             printPlainArray(0, tempIndexCount, tempIndex);
  370.         }
  371.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  372.             currentCount = (short)BLOCKCOUNT;
  373.             if (i + BLOCKCOUNT > tempIndexCount) {
  374.                 currentCount = (short)(tempIndexCount - i);
  375.             }
  376.             for (j = 0; j < currentCount; ++j) {
  377.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  378.             }
  379.             if (j == currentCount) break;
  380.         }
  381.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  382.             for (j = 1; j < i; ++j) {
  383.                 System.out.print(" ");
  384.             }
  385.             printPlainArray(start, BLOCKCOUNT, null);
  386.             System.out.println("    Found At: " + i);
  387.         }
  388.         return i;
  389.     }
  390.  
  391.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  392.     private static  final boolean DEBUGTRACE = false;
  393.     private static  final boolean DEBUGSMALL = false;
  394.     private static  final boolean DEBUGOVERLAP = false;
  395.     private static  final int DEBUGSMALLLIMIT = 30000;
  396.     private static  final int BLOCKSHIFT =7;
  397.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  398.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  399.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  400.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  401.  
  402.     private short values[];  // char -> short (char parameterized short)
  403.     private short indices[];
  404.     private boolean isCompact;
  405. };
  406.